/*
题目：滑动窗口的最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。
https://leetcode.cn/problems/sliding-window-maximum/
 */
public class MaxSlidingWindow {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<> (new ArrCmp());
        int[] ans = new int[nums.length - k + 1];
        int index = 0;//记录ans下标

        for (int i = 0; i < k; i++) {
            maxHeap.offer(new int[] {i, nums[i]});//储存下标和对应的值
        }
        ans[index++] = maxHeap.peek()[1];

        for (int i = k; i < nums.length; i++) {
            while (!maxHeap.isEmpty() && i - maxHeap.peek()[0] >= k) {
                maxHeap.poll();
            }
            maxHeap.offer(new int[] {i, nums[i]});
            ans[index++] = maxHeap.peek()[1];
        }

        return ans;
    }
}

class ArrCmp implements Comparator<int[]> {
    public int compare(int[] o1, int[] o2) {
        return o2[1] - o1[1];
    }
}
